import collections


class Solution:
    def checkWays(self, pairs: list) -> int:
        def dfs(adj, compos, seen, i, n):
            compos[i].add(n)
            seen.add(n)
            for neib in adj[n]:
                if neib not in seen:
                    dfs(adj, compos, seen, i, neib)

        def func(adj, nodes):
            degree = collections.defaultdict(list)
            m = len(nodes) - 1
            for node in nodes:
                degree[len(adj[node])].append(node)
            if len(degree[m]) == 0:
                return 0
            root = degree[m][0]
            for node in adj[root]:
                adj[node].remove(root)
            compos = collections.defaultdict(set)
            seen = set()
            i = 0
            for node in nodes:
                if node != root and node not in seen:
                    dfs(adj, compos, seen, i, node)
                    i += 1
            cands = [func(adj, compos[i]) for i in compos]
            if 0 in cands:
                return 0
            if 2 in cands:
                return 2
            if len(degree[m]) >= 2:
                return 2
            return 1

        adj = collections.defaultdict(set)
        for pair in pairs:
            adj[pair[0]].add(pair[1])
            adj[pair[1]].add(pair[0])
        return func(adj, set(adj.keys()))
